package 六查找;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Author XuZhuHong
 * @CreateTime 2021/9/22 18:22
 */
public class BinarySearch {
    private static ArrayList index = new ArrayList();

    public static void main(String[] args) {
        int[] array = new int[]{0, 0, 0, 3, 4, 5, 6, 7, 8, 9};
        System.out.println(Arrays.toString(array));
        int i1 = 0;//(int) (Math.random() * 10);
        index = binarySearch(array, i1, 0, array.length - 1);

        if (index.size() > 0) {

            System.out.println("查找到值为 " + i1 + " 的位置在" + index.toString());
        } else {

            System.out.println("没有找到值为 " + i1 + " 的数");
        }
    }

    public static ArrayList binarySearch(int[] array, int value, int left, int right) {
        if (left > right) {
            //没找到
            return index;
        } else {
            int mid = (left + right) / 2;
            if (array[mid] == value) {

                index.add(mid);

                for (int i = mid + 1; i <= right; i++) {
                    if (array[i] == value) {
                        index.add(i);
                    } else {
                        break;
                    }
                }
                for (int i = mid -1; i >= left; i--) {
                    if (array[i] == value) {
                        index.add(i);
                    } else {
                        break;
                    }
                }
                //返回下标
                return index;
            } else if (array[mid] > value) {
                return binarySearch(array, value, left, mid - 1);
            } else {
                return binarySearch(array, value, mid + 1, right);
            }
        }

    }
}
